'''
https://leetcode.cn/problems/last-stone-weight-ii/description/
'''
from typing import List

class Heap:
    def __init__(self, nums, comparator=lambda x, y: x < y):
        self.nums = list(nums) if nums else []
        self.size = len(self.nums)
        self.comparator = comparator
        for i in range((self.size - 2) // 2, -1, -1):
            self._heapify(i)

    def get_size(self):
        return self.size

    def empty(self):
        return self.size == 0

    def peek(self):
        if self.size == 0:
            return None
        return self.nums[0]

    def pop(self):
        if self.size == 0:
            return None
        nums = self.nums
        nums[0], nums[-1] = nums[-1], nums[0]
        res = nums.pop()
        self.size -= 1
        if self.size > 0:
            self._heapify(0)
        return res

    def push(self, v):
        self.nums.append(v)
        self._heap_insert(self.size)
        self.size += 1

    def pop_push(self, v):
        if self.empty():
            self.push(v)
            return None
        res = self.nums[0]
        self.nums[0] = v
        self._heapify(0)
        return res

    def push_pop(self, v):
        if self.empty() or self.comparator(v, self.nums[0]):
            return v
        res = self.nums[0]
        self.nums[0] = v
        self._heapify(0)
        return res

    def _heap_insert(self, i):
        nums = self.nums
        while (parent := (i - 1) // 2) >= 0 and self.comparator(nums[i], nums[parent]):
            nums[i], nums[parent] = nums[parent], nums[i]
            i = parent

    def _heapify(self, i):
        nums = self.nums
        size = self.size
        while (l := i * 2 + 1) < size:
            r = l + 1
            best = r if (r < size and self.comparator(nums[r], nums[l])) else l
            best = best if self.comparator(nums[best], nums[i]) else i
            if best == i:
                break
            nums[i], nums[best] = nums[best], nums[i]
            i = best

class Solution:

    # 模拟,从最强的出发，因为最后剩余的一定是小的
    def lastStoneWeight(self, stones: List[int]) -> int:
        heap = Heap(stones, lambda x, y: x > y)
        while heap.get_size() > 1:
            big = heap.pop()
            small = heap.pop()
            if big == small:
                continue
            else:
                heap.push(big - small)
        return 0 if heap.empty() else heap.peek()
